package meituan;

import java.util.Scanner;

/**
 * @Author Jun jie Yi
 * 2022/3/17 19:51
 */
public class Problem4 {

    public static int sum = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //结点数
        int N = sc.nextInt();
        //每个结点的值
        int[] arr = new int[N];
        //找到最大数的下标作为跟结点
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
            if (arr[max] < arr[i]) {
                max = i;
            }
        }
        //构造根节点
        Node root = new Node();
        root.val = arr[max];
        //构造树结构，0 找最大 1 找最小 (x + 1) % 2; -1 挂左边，1 右边
        buildTree(root, -1, arr, 0, max - 1, 1);
        buildTree(root, 1, arr, max + 1, N - 1, 1);
        getSumByMidOrder(root);
        System.out.println(sum);
    }
    //构造最优二叉树
    public static void buildTree(Node node, int direct, int[] arr, int l, int r, int flag) {
        if (l > r) {
            return;
        }
        //只有 2 个元素
        if (r - l == 1) {
            Node new_node;//记录结点
            Node new_node_l = new Node();
            Node new_node_r = new Node();
            new_node_l.val = arr[l];
            new_node_r.val = arr[r];
            if (arr[l] > arr[r]) {
                new_node_r.left = new_node_l;
                new_node = new_node_r;
            } else {
                new_node_l.right = new_node_r;
                new_node = new_node_l;
            }
            if (direct == -1) {
                node.left = new_node;
            } else {
                node.right = new_node;
            }
            return;
        }
        //只有 1 个元素
        if (l == r) {
            Node new_node = new Node();
            new_node.val = arr[l];
            if (direct == -1) {
                node.left = new_node;
            } else {
                node.right = new_node;
            }
            return;
        }
        int max = l;//找最大角标
        int min = l;//找最小角标
        for (int i = l; i <= r; i++) {
            if (arr[max] < arr[i]) {
                max = i;
            }
            if (arr[min] > arr[i]) {
                min = i;
            }
        }
        //标记大小转换
        int new_flag = (flag + 1) % 2;
        //最大
        if (flag == 0) {
            Node maxNode = new Node();
            maxNode.val = arr[max];
            //挂到父节点上
            if (direct == -1) {
                node.left = maxNode;
            } else {
                node.right = maxNode;
            }
            //该节点递归
            buildTree(maxNode, -1, arr, l, max - 1, new_flag);
            buildTree(maxNode, 1, arr, max + 1, r, new_flag);
            //最小
        } else {
            Node minNode = new Node();
            minNode.val = arr[min];
            //挂到父节点上
            if (direct == -1) {
                node.left = minNode;
            } else {
                node.right = minNode;
            }
            //该节点递归
            buildTree(minNode, -1, arr, l, min - 1, new_flag);
            buildTree(minNode, 1, arr, min + 1, r, new_flag);
        }

    }

    public static void getSumByMidOrder(Node node) {
        if (node.left != null) {
            sum += node.val * node.left.val;
            getSumByMidOrder(node.left);
        }
        if (node.right != null) {
            sum += node.val * node.right.val;
            getSumByMidOrder(node.right);
        }
    }
    //内部静态类的结点定义
    static class Node {
        Node left;
        Node right;
        int val;
    }

}
